package com.jhy.new2025.string;

/**
 * 给你两个字符串 haystack 和 needle
 * 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）
 * 。如果 needle 不是 haystack 的一部分，则返回  -1 。
 */

/**
 * 输入：haystack = "sadbutsad", needle = "sad"
 * 输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 */
public class StrStr {

    public static int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next, needle);
        // 下面的初始
        int j = -1;
        // 上面的指针
        for (int i = 0; i < haystack.length(); i++) {
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            if (j == needle.length() - 1) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }

    /**
     * 构造 next 数组的目的是找到 模式串中每个位置的最长相同前后缀的长度
     *
     * @param next
     * @param needle
     */
    public static void getNext(int[] next, String needle) {
        // 定义一个前缀
        int i = -1;
        // 因为第一个数组的前缀肯定是为-1
        next[0] = i;
        // j是我们的后缀
        for (int j = 1; j < needle.length(); j++) {
            // 如果当前不匹配 就找次长的来进行匹配因为 之前哪些长度是匹配过的
            // 一旦其中有个匹配成功 就停止 或者完全没有了
            while (i >= 0 && needle.charAt(j) != needle.charAt(i + 1)) {
                // 退回到前一个的前缀
                i = next[i];
            }
            // 如果遇到前后缀相等的 就移动前缀
            if (needle.charAt(i + 1) == needle.charAt(j)) {
                i++;
            }
            // 当前位置上的相同前后缀的数量
            next[j] = i;
        }
    }

    public static void main(String[] args) {
        String haystack = "aabaabaafa";
        String needle = "aabaaf";
        int[] next = new int[needle.length()];
        getNext(next, needle);
        System.out.println(strStr(haystack, needle));
    }
}
